package greedyAlgorithm;

import java.util.Arrays;

/**
 * @program: data_structures_algorithms
 * @description: 贪心算法：对每个子问题求解，得到子问题的局部最优解
 * 零钱找零问题
 * @author: lld
 * @create: 2020-11-19 16:36
 **/
public class ChangeMoney {
    public static void main(String[] args) {

        int[] count={3,0,2,1,0,3,5};//零钱数量
        int[] value={1,2,5,10,20,50,100};
        int change = change(79, count, value);
        if(change==-1){
            System.out.println("零钱不够，换不了");
        }else {
            System.out.println("至少用零钱数："+change);
            System.out.println(Arrays.toString(count));
        }
    }
    public static int change(int money,int[] count,int[] value){
        int num=0;
        for (int i = count.length-1; i >=0 ; i--) {
            int c=Math.min(money/value[i],count[i]);//判断零钱数量
            if(count[i]>0){//零钱数量-c
                count[i]-=c;
            }
            money=money-c*value[i];
            num+=c;
        }
        if(money>0){//换不了
            num=-1;
        }
        return num;
    }
}
